package nodelist

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn2925/
// 删除倒数第n个元素
// 算法: 先算出链表的总长度，然后直接找到第len-n 个元素
// 更优解法: 双指针，只需要遍历一次
func RemoveNthFromEnd(head *ListNode, n int) *ListNode {
	fastNode := moveNNode(head, n)
	currentNode, lastNode := head, head
	// 特殊情况: 倒数第n 个元素是空的，也就是已经到了队尾，这种情况下直接删除头即可
	if nil == fastNode {
		return head.Next
	}
	for nil != fastNode {
		fastNode = fastNode.Next
		lastNode = currentNode
		currentNode = currentNode.Next
	}
	if nil != currentNode {
		lastNode.Next = currentNode.Next
	}
	return head
}

func moveNNode(head *ListNode, n int) *ListNode {
	currentNode := head
	for n > 0 && currentNode != nil {
		currentNode = currentNode.Next
		n--
	}
	return currentNode
}
